雅可比符号

雅可比符号 $\bigl(\frac{a}{p}\bigr)$ 是勒让德符号在保持勒让德符号的同余性质、Gauss互反律等性质下的推广. 这里不要求 $p$ 必须是素数, $p$ 是正的奇数, $a$ 与其互素. 勒让德符号 $\bigl(\frac{a}{p}\bigr)$ 在计算过程中必须将分子 $a$ 进行因子分解, 在 $a$ 非常大时会比较麻烦, 这也导致函数 Legendre(a,p) 的实现比较复杂. 而这里的 Jacobi(a,p) 函数的实现就比较直接, 每当分子是偶数, 需要将因子 2 都提取出来, 即 $a=2^k b$ , 这里 $b$ 是奇数. 从而再应用Gauss互反律、同余性质进行计算, 将分母不断变小.

但某些情况下, 雅可比符号仍需要调用因子分解的程序. 例如当 $a=2$ 而奇数 $p$ 并非素数, 此时需要将 $p$ 进行因子分解.

Version: 0.536 已经实现 Jacobi(a,p) 函数.